백준 온라인 저지/출제된 문제/1991(r1 판)

상위 문서: 백준 온라인 저지/출제된 문제

트리 순회
문제 번호		1991
기여자		목록 확인
레이팅		Silver I
알고리즘		More 트리 재귀

1. 개요2. 풀이3. 정답 코드

3.1. Javascript

1. 개요 [편집]

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

대학교에서 처음 알고리즘 강의를 들으면 거의 100% 나오는 트리 개념에 대한 기초적인 문제이다.

2. 풀이 [편집]

문제에 표시된 예제 트리

전위 순회는 P(rint) - L(eft) - R(ight), 중위 순회는 L-P-R, 후위 순회는 L-R-P이므로 예제에 대하여 각각의 순회 방법을 적용한 결과는 다음과 같다.

순회 결과
전위 순회	A - B - D - C - E - F - G
중위 순회	D - B - A - E - C - F - G
후위 순회	D - B - E - G - F - C - A

이를 코드로 구현하기 위해서는 우선 입력을 받아 이를 트리 형태로 변환하여야 하는데, 라이브러리 없이 트리 구조를 기본적으로 지원하는 언어는 많지 않으므로 배열, 구조체 등의 방법을 활용하여야 한다. 문제에서 트리는 한 개의 노드에 대해 자식 노드가 최대 2개밖에 없는 이진 트리임이 보장되므로 입력으로 A B C를 받았다면 A: [B, C] 등으로 변환하는 것을 고려해볼 수 있다.

3. 정답 코드 [편집]

3.1. Javascript [편집]

코드 보기/접기

const [, ...wapas] = require('fs').readFileSync(0, 'utf8').trim().split('\n');

class Link {
  constructor(left, right) {
    this._left = left;
    this._right = right;
  }

  setLeft(left) {
    this._left = left;
  }

  setRight(right) {
    this._right = right;
  }

  getLeft() {
    return this._left;
  }

  getRight() {
    return this._right;
  }
};

let res = '';
const tree = {};
for (let i = 0; i < wapas.length; i++) {
  const [n, l, r] = wapas[i].split(' ');
  tree[n] = new Link(l, r);
}

const preorder = (n) => {
  if (n === '.') return;
  const link = tree[n];
  const [l, r] = [link.getLeft(), link.getRight()];
  res += n;
  preorder(l);
  preorder(r);
};

const inorder = (n) => {
  if (n === '.') return;
  const link = tree[n];
  const [l, r] = [link.getLeft(), link.getRight()];
  inorder(l);
  res += n;
  inorder(r);
};

const postorder = (n) => {
  if (n === '.') return;
  const link = tree[n];
  const [l, r] = [link.getLeft(), link.getRight()];
  postorder(l);
  postorder(r);
  res += n;
};

const root = Object.keys(tree).shift();

[preorder, inorder, postorder].forEach((func) => {
  func(root);
  console.log(res);
  res = '';
});